/*
Copyright (C) 2011 by the PSVN Research Group, University of Alberta
*/

#include <stdlib.h>
#include <stdio.h>
#include <inttypes.h>
#include <sys/time.h>
#include <dlfcn.h>
#include <assert.h>
#include <ctype.h>
#include "psvn_game_so.h"
#include "pdb.h"

#define TTABLE_MB 1024

//#define PRINT_SOLUTION

static int min(int a, int b)
{
    return (a < b) ? a : b;
}

typedef struct {
  int h_value;		/* if state has been searched before, we now
			   know a (potentially) better estimate of
			   the true distance to goal.  -1 if entry is unused */
  int8_t state[];
} tt_entry_t;

typedef struct {
  int32_t entry_size;
  int32_t size;		/* number of tt entries */
  void *entries;
} ttable_t;

uint64_t nodes_visited;

void clear_ttable( ttable_t *ttable )
{
  int32_t i;

  for( i = 0; i < ttable->size; ++i ) {

    ( (tt_entry_t *)( ttable->entries
		      + i * ttable->entry_size ) )->h_value = -1;
  }
}

ttable_t *new_ttable( const compiled_game_so_t *game,
		      const int32_t sizeMB )
{
  ttable_t *ttable;

  ttable = malloc( sizeof( *ttable ) );
  assert( ttable != NULL );

  ttable->entry_size = sizeof( tt_entry_t ) + game->state_size;
  ttable->size = (int64_t)sizeMB * 1048576 / ttable->entry_size;
  if( ttable->size < 1 ) {
    ttable->size = 1;
  }
  ttable->entries = malloc( ttable->entry_size * ttable->size );
  assert( ttable->entries != NULL );

  clear_ttable( ttable );

  return ttable;
}

/* update the transposition table with a new lower bound estimate */
void update_ttable( const compiled_game_so_t *game, ttable_t *ttable,
		    const void *state, const int h_value )
{
  int32_t idx;
  tt_entry_t *entry;

  idx = hash_so_state( state, game ) % ttable->size;
  entry = (tt_entry_t *)( ttable->entries + idx * ttable->entry_size );
  if( compare_so_states( state, entry->state, game ) == 0 ) {
    /* state is in table */

    if( h_value > entry->h_value ) {
      /* h_value is a larger lower bound */

      entry->h_value = h_value;
    }
  } else {
    /* state wasn't in table - overwrite */

    copy_so_state( entry->state, state, game );
    entry->h_value = h_value;
  }
}

/* get the lower bound estimate for a state
   returns -1 if the state is not in the table */
int check_ttable( const compiled_game_so_t *game, const ttable_t *ttable,
		  const void *state )
{
  int32_t idx;
  tt_entry_t *entry;

  idx = hash_so_state( state, game ) % ttable->size;
  entry = (tt_entry_t *)( ttable->entries + idx * ttable->entry_size );
  if( compare_so_states( state, entry->state, game ) != 0 ) {
    /* state not in table */

    return -1;
  }

  return entry->h_value;
}

int dfs_heur( const compiled_game_so_t *game, const void *pdb, 
              const void *state, ttable_t *ttable, 
              const int max_cost, int *min_need )
{
    int rule_used, h, h2;
    so_func_ptr iter;
    void *child;

    ++nodes_visited;
  
    h = (pdb != NULL) ? pdb_lookup( pdb, state, game ) : 0;
    h2 = (ttable != NULL) ? check_ttable( game, ttable, state ) : 0;
    if( h2 > h )
        h = h2;
    
    if( h > max_cost ) {
        *min_need = h;
        return 0;
    } else if( max_cost == 0 ) {
        if( is_so_goal( state, game ) ) {            
#ifdef PRINT_SOLUTION
            print_so_state( stdout, state, game );
            printf( "\n" );
#endif
            return 1;
        } else {
            *min_need = cost_of_cheapest_so_fwd_rule( game );
            return 0;
        }
    }
    
    *min_need = INT_MAX;
    child = new_so_state( game );
    init_so_fwd_iter( iter, game );
    while( ( rule_used = next_so_fwd_iter( iter, state ) ) >= 0 ) {
        apply_so_fwd_rule( rule_used, state, child, game );
        const int move_cost = game->fwd_rule_costs[ rule_used ];
        
        if (move_cost > max_cost)
            *min_need = min( *min_need, move_cost );
        else {
            int child_need;
            if( dfs_heur( game, pdb, child, ttable, 
                          max_cost - move_cost, &child_need ) ) 
            {
#ifdef PRINT_SOLUTION
                printf( "%s\n", game->fwd_rule_names[ rule_used ] );
                print_so_state( stdout, state, game );
                printf( "\n" );
#endif
                return 1;
            }
            *min_need = min ( *min_need, move_cost + child_need );
        }
    }
    assert( *min_need > max_cost );
    destroy_so_state( child );    
    if (ttable != NULL) 
        update_ttable( game, ttable, state, *min_need );
    return 0;
}

int idastar( const compiled_game_so_t *game, const void *pdb, 
             const void *state, ttable_t *ttable, int64_t *total_nodes )
{
    int max_cost, done;

    max_cost = 0; 
    if ( pdb != NULL ) 
        max_cost = pdb_lookup( pdb, state, game );

    *total_nodes = 0;
    while (1) {
        int need;
        nodes_visited = 0;            
        done = dfs_heur( game, pdb, state, ttable, max_cost, &need );

        printf( "search cost %d: %ld\n", max_cost, nodes_visited );
        *total_nodes += nodes_visited;        
        if( done )
            break;
        assert( need > max_cost );
        max_cost = need;
    }
    return max_cost;
}

void get_state_space_name(const char* in, char* out)
{
    const char* str = strrchr(in, '/');
    if (*str == 0)
        str = in;
    str++;
    while (*str && (isalpha(*str) || isdigit(*str) || *str=='_')) {
        *out++ = *str++;
    }
    *out = 0;
}

int main( int argc, char **argv )
{
    void *so_handle, *state;
    int64_t visited, total_visited;
    int trials, d, total_d;
    compiled_game_so_t *game;
    void *pdb = NULL;
    ttable_t *ttable = NULL;
    char line[ 4096 ];
    struct timeval start, end;
    
    /* read the game */
    if( argc < 2 ) {
        fprintf( stderr, "requires a shared game object\n" );
        exit( EXIT_FAILURE );
    }
    so_handle = dlopen( argv[ 1 ], RTLD_LAZY );
    if( so_handle == NULL ) {
        fprintf( stderr, "could not open shared object %s: %s\n",
                 argv[ 1 ], dlerror() );
        exit( EXIT_FAILURE );
    }
    char name[1024];
    get_state_space_name(argv[1], name);
    game = dlsym( so_handle, name);
    if (game == NULL) {
        game = dlsym( so_handle, "psvn_state_space" );
        if( game == NULL ) {
            fprintf( stderr, "could not read game object from %s\n", argv[ 1 ] );
            exit( EXIT_FAILURE );
        }
    }
    
    /* read the pattern database */
    if( argc > 2 ) {
        pdb = read_pdb( argv[2], game );
        if (pdb == NULL)
            return EXIT_FAILURE;
    } else {
        pdb = NULL;
    }

#ifdef TTABLE_MB
    ttable = new_ttable( game, TTABLE_MB );
#endif

    state = new_so_state( game );
    total_d = 0;
    total_visited = 0;
    gettimeofday( &start, NULL );
    for( trials = 0;
         fgets( line, 4096, stdin ) != NULL
             && read_so_state( line, state, game ) > 0;
         ++trials ) {
        
        printf( "problem %d: ", trials + 1 );
        print_so_state( stdout, state, game );
        printf( "\n" );
        
        d = idastar( game, pdb, state, ttable, &visited );

        printf( "depth %d nodes %lu\n", d, visited );
        total_d += d;
        total_visited += visited;
    }
    gettimeofday( &end, NULL );
    destroy_so_state( state );
    
    end.tv_sec -= start.tv_sec;
    end.tv_usec -= start.tv_usec;
    if( end.tv_usec < 0 ) {
        end.tv_usec += 1000000;
        --end.tv_sec;
    }

    printf( "total: depth %d nodes %lu %zd.%06zd seconds\n",
            total_d, total_visited, end.tv_sec, end.tv_usec );
    
    if( pdb != NULL )
        destroy_pdb( pdb, game );
    
    return EXIT_SUCCESS;
}
